#include "map.h"
#include <malloc.h>
#include <assert.h>
#include <string.h>

C_CODE_BEGIN
/*
 * I assume that the sizeof(map_slot) >= sizeof(freelist)
 * and this must be true !
 */

struct freelist {
	struct freelist* prev;
	struct freelist* next;
	// this tag is very important to identify a free list is really a free list or a used slots
	void* tag[2];
};

struct map_slot {
	// hash value for this slots
	size_t fhash; 
	char key[NAME_MAX_LEN] ;
	size_t klen;
	struct map_slot* next;
} ;


#define MAP_SLOT_SIZE(objsize)  \
((objsize) + (sizeof( struct map_slot) >= sizeof(struct map_slot) ? sizeof(struct map_slot) : sizeof(struct freelist)))

#define MAP_VALUE_BUF(slot) \
	((char*)(slot) +sizeof(struct map_slot))

#define USED_MASK (void*)(0xffffffff)

#define IS_USED(sl) \
	( ((struct freelist*)(sl))->tag[0] != USED_MASK ||  ((struct freelist*)(sl))->tag[1] != USED_MASK  )

struct map {
	struct  map_slot * sentry ;
	size_t size;
	size_t usize;
	size_t objsize;
	// hash function for this map
	size_t (*hash_func)( const char* );
	struct freelist* fltail;
	// the real buffer start pointer
	void* buffer;
};

static void  _build_free_list( struct map* m  ) {
	size_t i = 0;
	
	struct freelist* dmy = (struct freelist*)(m->buffer);
	struct freelist* cur = dmy+1;
	m->sentry = (struct map_slot*)(cur);
	
	m->fltail = dmy;
	m->fltail->next = m->fltail;
	m->fltail->prev = m->fltail;
	for( ; i < m->size ; ++i ) {
			cur->next = m->fltail;
			cur->prev = m->fltail->prev;
			m->fltail->prev->next = cur;
			m->fltail->prev = cur;
			cur->tag[0] = cur->tag[1] = USED_MASK;
			cur = (struct freelist*)( (char*)(cur) + MAP_SLOT_SIZE(m->objsize) );
	}
}

static void _put_back_freelist( struct map* m , struct map_slot* ms ) {
	struct freelist* fs = (struct freelist*)(ms);
	fs->next = m->fltail->next;
	m->fltail->next->prev = fs;
	fs->prev = m->fltail;
	m->fltail->next = fs;
	fs->tag[0] = fs->tag[1]  = USED_MASK;
}

static void _release_from_freelist( struct map* m , struct map_slot* ms ) {
	struct freelist* fl = (struct freelist*)ms;
	assert( !IS_USED(ms) );
	fl->prev->next = fl->next;
	fl->next->prev = fl->prev;
	fl->tag[1]=fl->tag[2]=NULL;
}

static struct map_slot* _fetch_from_freelist( struct map* m ) {
	struct freelist* ret;
	assert( m->fltail->next != m->fltail );
	ret = m->fltail->next;
	ret->next->prev = m->fltail;
	m->fltail->next=ret->next;
	return (struct map_slot*)ret;
}

static struct map_slot* _malloc_map_slot( struct map* m) {
	return _fetch_from_freelist(m);
} 

static void _free_map_slot( struct map* m , struct map_slot* sl ) {
	_put_back_freelist(m,sl);
}


static size_t _def_hfunc( const char* k) {
	size_t len = strlen(k);
	size_t ha = len;
	size_t loop =(len>> 3 )+1;
	size_t i ;
	for( i = len ; i >= loop ; i-= loop )
		ha = ha ^ ((ha<<5)+(ha>>2)+(size_t)(k[i-1]));
	return ha;
}

EXPORT_FUNC struct map* map_create( size_t objsize , size_t initial_slot , size_t (*hash_func ) (const char*) ) {
	struct map* ret = malloc( sizeof( struct map ) );
	initial_slot == 0 ? 1 : initial_slot;
	ret->buffer= malloc( MAP_SLOT_SIZE(objsize) * initial_slot + sizeof( struct freelist) );
	ret->objsize = objsize;
	ret->size = initial_slot;
	ret->usize= 0;
	ret->hash_func = (hash_func == NULL ? _def_hfunc : hash_func);
	_build_free_list(ret);
	return ret;
}

static void _rehash( struct map* m );

static  void* _map_insert ( struct map* m ,  struct map_slot* s , void* v , const char** key_ref ) {
	size_t idx;
	struct map_slot* sl;
	struct map_slot* tempsl;
	if( m->size == m->usize ) {
		_rehash(m);
	} 
	idx = (s->fhash) % (m->size);
	sl = (struct map_slot*)( (char*)(m->sentry) + idx*(MAP_SLOT_SIZE(m->objsize)) );
	if( IS_USED(sl) ) {
		tempsl = sl;
		sl = _malloc_map_slot(m);
		// finding out the insertion position
		while( tempsl->next != NULL ) {
			if( tempsl->fhash == s->fhash && strcmp( tempsl->key , s->key ) ==0 ) 
				goto __ERROR;
			tempsl = tempsl->next;
		}
		tempsl->next = sl;
		sl->next = NULL;
	} else {
		// must release it from the freelist
		_release_from_freelist(m,sl);
		sl->next = NULL;
	}
	
	sl->fhash = s->fhash;
	sl->klen = s->klen;
	strcpy( sl->key , s->key );
	// copy the value here
	memcpy( MAP_VALUE_BUF(sl) , v , m->objsize );
	if( key_ref )
		*key_ref = sl->key;
	++(m->usize);
	return MAP_VALUE_BUF(sl);
	
__ERROR:
	_put_back_freelist( m , sl );
	return NULL;
}

struct rehash_arg {
	struct map* src;
	struct map* des;
};


static void _map_until( struct map* m , bool (*func)( struct map_slot* , void* var), void* var) {
	size_t i = 0 ; 
	struct map_slot* sl = m->sentry;
	for( ; i < m->size ; ++i ) {
		if( IS_USED(sl) ) {
			if( func( sl , var ) == false )
				return;
		}
		sl = (struct map_slot*)( (char*)(sl) + MAP_SLOT_SIZE(m->objsize) );
	}
}

struct mfw_arg{
	void* arg;
	void (*func)(struct map_kv* , void* args);
};

static bool _map_foreach_wrapper ( struct map_slot* sl , void* var )  {
	struct mfw_arg * ar = ( struct mfw_arg* )(var);
	struct map_kv kv ;
	kv.key = sl->key;
	kv.val = MAP_VALUE_BUF(sl);
	ar->func( &kv , ar->arg);
	return true;
}

EXPORT_FUNC void map_foreach( struct map* m , void (*func)(struct map_kv* , void* args), void* args ) {
	struct mfw_arg a;
	a.arg = args;
	a.func=func;
	_map_until( m , _map_foreach_wrapper , &a);
}


struct muw_args {
	void* arg;
	bool (*func)( struct map_kv* , void* args );
};

static bool _map_until_wrapper ( struct map_slot* sl , void* args ) {
	struct muw_args* ar = ( struct muw_args* )(args);
	struct map_kv kv;
	kv.key = sl->key;
	kv.val = MAP_VALUE_BUF(sl);
	return ar->func( &kv,ar->arg );
}

EXPORT_FUNC void map_until( struct map* m, bool (*func)( struct map_kv* , void* args ) ,void* args ) {
	struct muw_args a;
	a.arg=args;
	a.func =func;
	_map_until( m , _map_until_wrapper , &a );
}

static bool  _rehash_foreach( struct map_slot* kv , void* var ) {
	struct rehash_arg * ar = (struct rehash_arg *)(var);
	_map_insert(ar->des,kv, MAP_VALUE_BUF(kv),NULL) ;
	// the owned key should not be deleted 
	return true;
}

static void _rehash( struct map* m ) {
	struct map tpm;
	struct rehash_arg args;
	args.src = m;
	args.des = &tpm;
	// build a dummy map
	tpm.objsize = m->objsize;
	tpm.usize = 0;
	tpm.size = (m->size)*2;
	tpm.buffer = malloc( MAP_SLOT_SIZE(m->objsize) *tpm.size +sizeof(struct freelist) );
	tpm.hash_func = m->hash_func;
	_build_free_list(&tpm);
	_map_until( m , _rehash_foreach , &args);
	free( m->buffer );
	m->sentry = tpm.sentry;
	m->size = tpm.size;
	m->fltail = tpm.fltail;
	m->buffer = tpm. buffer;
}

EXPORT_FUNC void* map_insert( struct map* m, const struct map_kv* kv , const char** key_ref) {
	struct map_slot sl;
	sl.fhash = m->hash_func(kv->key);
	sl.klen = strlen( kv->key ) ;
	if( sl.klen >= 64 ) {
		return NULL;
	}
	strcpy( (char*)&(sl.key) , kv->key );
	return _map_insert(m,&sl,kv->val,key_ref);
}


static struct map_slot* _map_query ( struct map* m  ,const char* k ) {
	size_t hash = m->hash_func(k);
	size_t idx = hash % (m->size);
	struct map_slot* sl = ( struct map_slot* ) ( (char*)(m->sentry) + MAP_SLOT_SIZE(m->objsize)*idx );
	/* find a empty entry */
	/* BUGS: I have forgotten to deal with this situation which cause a very complicated bug later on */
	if( !IS_USED(sl) )
		return NULL;
	while( sl ) {
		if( sl->fhash == hash && strcmp(sl->key,k) == 0 ) {
			return sl;
		}
		sl = sl->next;
	}
	return NULL;
}

EXPORT_FUNC const char* map_key_ref( struct map* m, const char* k ) {
	struct map_slot* ms = _map_query(m,k);
	if(ms == NULL)
		return NULL;
	return ms->key;
}

EXPORT_FUNC void* map_query( struct map* m , const char* k , const char** key_ref ) {
	struct map_slot* sl = _map_query(m,k);
	if(key_ref)
		*key_ref = sl->key;
	return sl == NULL ? NULL : MAP_VALUE_BUF(sl);
}

EXPORT_FUNC bool map_remove( struct map* m , const char* k ) {
	struct map_slot* sl = _map_query(m,k);
	assert( m->usize > 0 );
	if( sl == NULL ) {
		return false;
	}
	_free_map_slot(m,sl);
	-- (m->usize);
	return true;
}


static bool _map_clear( struct map_slot* sl , void* arg ) {
	_free_map_slot((struct map*)(arg),sl);
	return true;
}

EXPORT_FUNC void map_clear( struct map* m  ) {
	_map_until( m , _map_clear , m);
}

EXPORT_FUNC void map_destroy( struct map* m ) {
	map_clear(m);
	free(m->buffer);
	free(m);
}

EXPORT_FUNC size_t map_get_usesize( struct map* m ) {
	return m->usize;
}



C_CODE_END